# -*-coding = utf-8 -*-

# @Time: 2021/4/6 0:13
# @Author: bistro
# @File: p80.py
# @Software: PyCharm
from typing import List


#  删除有序数组中的重复项 II
class Solution:
    """
    时间：O(n) 中间删除耗时增加
    空间：O(n) 字典计数
    """
    def removeDuplicates(self, nums: List[int]) -> int:
        nums_dict = {}
        for i, v in enumerate(nums[::-1]):
            temp = nums_dict.get(v, 0)
            if temp < 2:
                nums_dict[v] = nums_dict.get(v, 0) + 1
            else:
                nums.remove(v)
        print(nums)
        return len(nums)

    # 可作为删除重复元素通用模板，不论几个
    """
    时间：O(n)
    空间：O(1)
    """
    def removeDuplicates1(self, nums: List[int]) -> int:
        i = 0
        for num in nums:
            if i < 2 or num != nums[i-2]:
                nums[i] = num
                i += 1
        return i


# 测试语句
s = Solution()
s.removeDuplicates([0, 0, 1, 1, 1, 1, 2, 3, 3])
